// 字符串算法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/// @brief 匹配子串sub在原字符串origin中的下标（使用暴力匹配）
/// @param origin 原字符串
/// @param sub 子串
/// @return 子串在原字符串中位置，不存在返回-1
int BFMatch(char origin[], char sub[])
{
	int i = 0, j = 0, originLength = strlen(origin), subLength = strlen(sub);
	while (i < originLength && j < subLength)
	{
		// 若当前匹配上了
		if (origin[i] == sub[j])
		{
			i++;
			j++;
			continue;
		}
		// 否则，i回退到i这一趟最开始匹配时的后一位，j回退到0
		i = i - j + 1;
		j = 0;
	}
	if (j > subLength - 1)
	{
		return i - subLength;
	}
	// 否则说明匹配失败
	return -1;
}

/// @brief 求得KMP算法中的next数组
/// @param sub 子串
/// @param next 存放next数组结果
void getNext(char sub[], int next[])
{
	int m = 0, n = 1, length = strlen(sub);
	next[m] = -1;
	next[n] = 0;
	while (n < length)
	{
		if (m == -1 || sub[m] == sub[n])
		{
			m++;
			n++;
			next[n] = m;
		}
		else if (sub[m] != sub[n])
		{
			m = next[m];
		}
	}
}

/// @brief 字符串匹配-KMP算法
/// @param origin 原字符串
/// @param sub 子串
/// @return 子串在原字符串中位置，不存在返回-1
int KMPMatch(char origin[], char sub[])
{
	int originLength = strlen(origin), subLength = strlen(sub);
	int i = 0, j = 0, next[subLength];
	getNext(sub, next);
	while (i < originLength && j < subLength)
	{
		if (next[j] == -1 || origin[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j > subLength - 1)
	{
		return i - subLength;
	}
	return -1;
}

/// @brief 反转字符串
/// @param str 原字符串
void *reverse(char str[])
{
	int i = 0, j = strlen(str) - 1;
	char temp;
	while (i < j)
	{
		temp = str[i];
		str[i] = str[j];
		str[j] = temp;
		i++;
		j--;
	}
}

/// @brief 求字符串的最长回文字符串
/// @param str 原字符串
/// @return 字符串的最长回文字符串
char *maxPalindromeString(char str[])
{
	// 使用中心扩展法
	// 从每一个位置出发，向两边扩散，直到不回文结束
	// 遍历每个字符，遍历的时候，以当前字符开始往左寻找相同的字符，直到不同为止
	// 再往右寻找相同的字符，直到不同为止
	// 再左右双向扩散，直到左右两者不相等为止
	if (str == NULL)
	{
		return NULL;
	}
	// 遍历下标，左右指针，字符串长度，最大回文串起始下标，最大回文串长度，当前字符串长度
	int i, left, right, length = strlen(str), maxStart, maxLength = 0, currentLength;
	// 开始遍历每一个字符串
	for (i = 0; i < length; i++)
	{
		currentLength = 1;
		// 先往左扩展
		left = i - 1;
		while (left >= 0 && str[left] == str[i])
		{
			left--;
			currentLength++;
		}
		// 再往右扩展
		right = i + 1;
		while (right < length && str[right] == str[i])
		{
			right++;
			currentLength++;
		}
		// 最后双向扩展
		while (left >= 0 && right < length && str[left] == str[right])
		{
			left--;
			right++;
			currentLength += 2;
		}
		// 统计最大
		if (currentLength > maxLength)
		{
			maxLength = currentLength;
			// left指向了第一个导致不回文的字符串，因此+1
			maxStart = left + 1;
		}
	}
	// 返回结果
	char *result = (char *)calloc(maxLength + 1, sizeof(char));
	for (i = 0; i < maxLength; i++)
	{
		result[i] = str[maxStart++];
	}
	result[i] = '\0';
	return result;
}

int main()
{
	return 0;
}